package com.explorati.LeetCode101.SymmetricTree;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 101. Symmetric Tree 判断一棵树是否是镜像的
 * 
 * 详情见：https://leetcode.com/problems/symmetric-tree/
 * 
 * @author explorati
 *
 */
public class Solution {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public boolean isSymmetric(TreeNode root) {
		if (root == null) {
			return true;
		}
		return compareTwoNodes(root.left, root.right);
	}

	public static boolean compareTwoNodes(TreeNode p, TreeNode q) {
		if (p == null && q == null) {
			return true;
		} else if (p == null || q == null) {
			return false;
		} else if (p.val == q.val) {
			return compareTwoNodes(p.left, q.right) && compareTwoNodes(p.right, q.left);
		} else {
			return false;
		}

	}

	// 不能使用层序遍历，因为每层的元素个数是不确定的，转成list之后也没办法
	// public static List<Integer> traverseTree(TreeNode root) {
	// List<Integer> list = new ArrayList<>();
	// Queue<TreeNode> queue = new LinkedBlockingQueue<>();
	// TreeNode cur = null;
	// queue.add(root);
	// while (!queue.isEmpty()) {
	// cur = queue.poll();
	// list.add(cur.val);
	// if (cur.left != null) {
	// queue.add(cur.left);
	// }
	// if (cur.right != null) {
	// queue.add(cur.right);
	// }
	// }
	// return list;
	// }
}
